<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最长公共子序列 | 算法可视化</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
            line-height: 1.6;
        }
        .hero {
            background: linear-gradient(135deg, #3b82f6 0%, #1d4ed8 100%);
        }
        .code-block {
            background-color: #1e293b;
            color: #e2e8f0;
            border-radius: 0.5rem;
            overflow: hidden;
        }
        .code-header {
            background-color: #0f172a;
            padding: 0.75rem 1rem;
            display: flex;
            align-items: center;
        }
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
            margin-right: 8px;
        }
        .code-dot-red {
            background-color: #ef4444;
        }
        .code-dot-yellow {
            background-color: #f59e0b;
        }
        .code-dot-green {
            background-color: #10b981;
        }
        .card {
            transition: transform 0.3s ease, box-shadow 0.3s ease;
        }
        .card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            background: linear-gradient(90deg, rgba(59, 130, 246, 0.1) 0%, rgba(59, 130, 246, 0) 100%);
            border-left: 4px solid #3b82f6;
        }
    </style>
</head>
<body class="min-h-screen">
    <!-- Hero Section -->
    <section class="hero text-white py-20 px-4 md:px-8">
        <div class="max-w-5xl mx-auto">
            <div class="flex flex-col md:flex-row items-center">
                <div class="md:w-1/2 mb-10 md:mb-0">
                    <h1 class="text-4xl md:text-5xl font-bold mb-4 font-serif">最长公共子序列</h1>
                    <p class="text-xl mb-6 opacity-90">探索动态规划在字符串处理中的精妙应用</p>
                    <div class="flex items-center">
                        <span class="bg-white text-blue-600 px-4 py-2 rounded-full font-medium mr-4">算法</span>
                        <span class="bg-white text-blue-600 px-4 py-2 rounded-full font-medium">动态规划</span>
                    </div>
                </div>
                <div class="md:w-1/2">
                    <div class="bg-white bg-opacity-10 p-6 rounded-xl backdrop-blur-sm">
                        <div class="mermaid">
                            graph TD
                                A[开始] --> B[初始化DP数组]
                                B --> C[i从1到m]
                                C --> D[j从1到n]
                                D --> E{text1[i]==text2[j]}
                                E -->|是| F[dp[i][j]=dp[i-1][j-1]+1]
                                E -->|否| G[dp[i][j]=max(dp[i-1][j],dp[i][j-1])]
                                G --> D
                                F --> D
                                D --> H[返回dp[m][n]]
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-5xl mx-auto px-4 md:px-8 py-12">
        <!-- Problem Section -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-2 h-8 bg-blue-600 mr-3"></div>
                <h2 class="text-2xl font-bold font-serif">题目描述</h2>
            </div>
            <div class="bg-white rounded-xl shadow-md p-6 mb-8">
                <p class="text-lg mb-4">给定两个字符串 <span class="font-mono bg-gray-100 px-2 py-1 rounded">text1</span> 和 <span class="font-mono bg-gray-100 px-2 py-1 rounded">text2</span>，返回这两个字符串的<strong>最长公共子序列</strong>的长度。如果不存在公共子序列，则返回 0。</p>
                <p class="text-lg mb-4">一个字符串的<strong>子序列</strong>是指删除原字符串中的某些字符（也可能不删除）后，剩余字符保持相对顺序形成的新字符串。</p>
                <div class="highlight p-4 rounded-lg mb-4">
                    <p class="flex items-center"><i class="fas fa-lightbulb text-yellow-500 mr-2"></i> <strong>示例：</strong> <span class="font-mono bg-blue-100 text-blue-800 px-2 py-1 rounded ml-2">"ace"</span> 是 <span class="font-mono bg-blue-100 text-blue-800 px-2 py-1 rounded">"abcde"</span> 的子序列</p>
                </div>
                <div class="grid grid-cols-1 md:grid-cols-2 gap-4">
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <p class="text-gray-600 mb-2">输入:</p>
                        <p class="font-mono">text1 = "abcde", text2 = "ace"</p>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <p class="text-gray-600 mb-2">输出:</p>
                        <p class="font-mono">3</p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Solution Section -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-2 h-8 bg-blue-600 mr-3"></div>
                <h2 class="text-2xl font-bold font-serif">解题思路</h2>
            </div>
            <div class="grid grid-cols-1 md:grid-cols-3 gap-6 mb-8">
                <div class="card bg-white rounded-xl shadow-md p-6">
                    <div class="text-blue-600 mb-4">
                        <i class="fas fa-project-diagram text-3xl"></i>
                    </div>
                    <h3 class="font-bold text-xl mb-3">动态规划</h3>
                    <p class="text-gray-600">使用二维动态规划数组来存储子问题的解，避免重复计算。</p>
                </div>
                <div class="card bg-white rounded-xl shadow-md p-6">
                    <div class="text-blue-600 mb-4">
                        <i class="fas fa-table text-3xl"></i>
                    </div>
                    <h3 class="font-bold text-xl mb-3">状态定义</h3>
                    <p class="text-gray-600">dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度。</p>
                </div>
                <div class="card bg-white rounded-xl shadow-md p-6">
                    <div class="text-blue-600 mb-4">
                        <i class="fas fa-code-branch text-3xl"></i>
                    </div>
                    <h3 class="font-bold text-xl mb-3">状态转移</h3>
                    <p class="text-gray-600">比较当前字符是否相同，分别处理两种情况。</p>
                </div>
            </div>

            <div class="bg-white rounded-xl shadow-md p-6 mb-8">
                <h3 class="font-bold text-xl mb-4 font-serif">算法步骤详解</h3>
                <div class="space-y-4">
                    <div class="flex items-start">
                        <div class="bg-blue-100 text-blue-800 rounded-full w-8 h-8 flex items-center justify-center flex-shrink-0 mr-3">1</div>
                        <div>
                            <p class="font-medium">定义 dp[i][j] 为 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。</p>
                        </div>
                    </div>
                    <div class="flex items-start">
                        <div class="bg-blue-100 text-blue-800 rounded-full w-8 h-8 flex items-center justify-center flex-shrink-0 mr-3">2</div>
                        <div>
                            <p class="font-medium">若 text1[i] 等于 text2[j]，则 dp[i][j] = dp[i-1][j-1] + 1</p>
                        </div>
                    </div>
                    <div class="flex items-start">
                        <div class="bg-blue-100 text-blue-800 rounded-full w-8 h-8 flex items-center justify-center flex-shrink-0 mr-3">3</div>
                        <div>
                            <p class="font-medium">否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])</p>
                        </div>
                    </div>
                    <div class="flex items-start">
                        <div class="bg-blue-100 text-blue-800 rounded-full w-8 h-8 flex items-center justify-center flex-shrink-0 mr-3">4</div>
                        <div>
                            <p class="font-medium">时间复杂度：O(m×n)，空间复杂度：O(m×n)</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Section -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="w-2 h-8 bg-blue-600 mr-3"></div>
                <h2 class="text-2xl font-bold font-serif">示例代码</h2>
            </div>
            <div class="code-block rounded-xl mb-8">
                <div class="code-header">
                    <div class="code-dot code-dot-red"></div>
                    <div class="code-dot code-dot-yellow"></div>
                    <div class="code-dot code-dot-green"></div>
                    <div class="ml-2 text-gray-400 text-sm">LongestCommonSubsequence.java</div>
                </div>
                <div class="p-6 overflow-x-auto">
                    <pre class="text-sm md:text-base"><code class="language-java">public int longestCommonSubsequence(String text1, String text2) {
    // 获取两个字符串的长度
    int m = text1.length();
    int n = text2.length();
    
    // 创建二维动态规划数组，dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度
    int[][] dp = new int[m + 1][n + 1];
    
    // 填充dp数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 如果当前字符相同，则最长公共子序列长度加1
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 否则取text1少一个字符或text2少一个字符的最长公共子序列的较大值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 返回两个字符串的最长公共子序列长度
    return dp[m][n];
}</code></pre>
                </div>
            </div>
        </section>

        <!-- Visualization Section -->
        <section>
            <div class="flex items-center mb-6">
                <div class="w-2 h-8 bg-blue-600 mr-3"></div>
                <h2 class="text-2xl font-bold font-serif">动态规划表格可视化</h2>
            </div>
            <div class="bg-white rounded-xl shadow-md p-6">
                <div class="mermaid">
                    %%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#eff6ff', 'primaryBorderColor': '#3b82f6', 'lineColor': '#3b82f6'}}}%%
                    flowchart TD
                        subgraph DP表格
                            direction TB
                            A["dp[i][j]"] --> B[" "]
                            B --> C["a"]
                            C --> D["b"]
                            D --> E["c"]
                            E --> F["d"]
                            F --> G["e"]
                            
                            H[" "] --> I["0"] --> J["0"] --> K["0"] --> L["0"] --> M["0"] --> N["0"]
                            O["a"] --> P["0"] --> Q["1"] --> R["1"] --> S["1"] --> T["1"] --> U["1"]
                            V["c"] --> W["0"] --> X["1"] --> Y["1"] --> Z["2"] --> AA["2"] --> AB["2"]
                            AC["e"] --> AD["0"] --> AE["1"] --> AF["1"] --> AG["2"] --> AH["2"] --> AI["3"]
                        end
                </div>
                <div class="mt-6 text-gray-600">
                    <p><i class="fas fa-info-circle text-blue-500 mr-2"></i> 上表展示了当 text1="abcde" 和 text2="ace" 时的动态规划表格。最终结果为右下角的数字 3。</p>
                </div>
            </div>
        </section>
    </main>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: false,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>